1. Technical Field
The present application relates generally to an improved data processing apparatus and method. More specifically, the present application is directed to an apparatus and method for multi-hit detection in associative memories, such as a content addressable memory (CAM).
2. Description of Related Art
A content addressable memory (CAM) is a type of associative memory having an individual logic circuit associated with each memory cell or CAM entry. The individual logic circuits of each memory cell allow for simultaneously comparing the contents of each memory cell of the CAM in a single memory cycle. Because the entire contents of the CAM memory can be searched in one memory cycle, such memories may perform fast searches. CAM memory is especially useful for cache memory as a lookup table to point to an information location for information stored in conventional RAM (random access memory) memory, for example.
FIG. 1 illustrates an example of a known CAM array 100 comprising multiple memory cells 110. The CAM array 100 may be used for various purposes in which quick searching of multiple entries is desirable. For example, CAM arrays are typically used to provide address translation or address resolution, such as for cache accesses.
The memory cells 110 are arranged as an array having rows 120 and columns 130. The rows 120 of the CAM array 100 may sometimes be referred to as “word lines.” The memory cells 110 in a particular row 120 are connected to one another by a match line 114. The match lines 114 of each row 120 are also connected to a hit logic circuit 140 which receives the output from the rows of memory cells 110 and determines which rows result in a match or “hit.” The memory cells 110 in a particular column 130 are connected to one another by search lines 134. The search lines 134 couple the output of the search drivers 150 to the input of the memory cells 110. An output 142 of the hit logic circuit 140 is connected to the input of a secondary storage table memory 160, which may be a RAM, SRAM, or the like, which receives the outputs from the hit logic circuit 140 and outputs a corresponding data entry. The hit logic circuit 140 may also output a hit/miss signal 144 to indicate whether there was a hit detected or not.
In operation, the match lines 114 are pre-charged to a high state in preparation for a next search cycle. The search drivers 150 input the search data into the CAM array 100 through the search lines 134. This search data may be, for example, an input address for address translation or resolution. If the memory cell 110 does not contain the target data, the memory cell 110 causes its associated match line 114 to discharge to ground. If the contents of a particular cell 110 match the applied data received, along its search line 134, the memory cell 110 will allow its match line 114 to remain high. Thus, if all the memory cells 110 in a row 120 match the search data received on the search lines 134, the match line 114 of that row 130 remains high indicating a match. Otherwise, the match line 114 is discharged to ground indicating a mismatch or miscompare, in at least one of the cells 110 on the match line 114.
Based on the particular row 120 in the array 100 that that indicates a “hit,” a corresponding row in the secondary storage table memory 160 is selected. That is, the data in the secondary storage table memory 160 may be indexed by the stored address table represented by the CAM array 100. The corresponding data in the secondary storage table memory 160 may then be output for use by the computing system in which the CAM array 100 is present. This is referred to as a “match read.” The above operation may then be repeated for the next search cycle.
As noted above, a benefit of a CAM array is its ability to search all entries simultaneously. For example, a CAM array that has 1K entries can be searched in one cycle, while a standard memory (SRAM or DRAM) would typically require 1000 cycles to determine if the desired data is present.
However, one limitation of CAM systems is that, at most, only one word line stored in the device should be matched at a time. Nevertheless, a significant problem with existing CAM devices is that a circuit failure or software error external to the CAM device can cause the occurrence of multiple “hits.” For example, in devices used in certain environments, radiation may cause soft error rate (SER) failures of the CAM device. As one example, alpha particles that are typically filtered out by Earth's atmosphere, may cause SER failures of CAM devices in applications where such filtering is not possible, such as in satellites, space vehicles, and other devices intended for use outside of Earth's atmosphere or at very high altitudes.
If a multiple hit condition exists, multiple word-lines are enabled in the CAM device and erroneous outputs are returned. That is, multiple data entries in the secondary storage table memory 160 are simultaneously accessed causing the resulting data output to be invalid. Even worse, data corruption in the secondary storage table memory 160 may result if the access involves shared read/write bitlines.
Thus, it is important to be able to detect the occurrence of a multiple hit condition in a CAM device. A known solution for detecting the multiple hit condition in a CAM device is to use a system of logical XOR gates to detect the multiple hit condition. With this known solution, each row in the secondary storage table memory 160, i.e. the RAM side of the CAM structure, is assigned a unique address. This address and its complement are stored in a ROM table (not shown). Whenever there is a “hit” in the CAM array 100, i.e. the CAM side of the CAM structure, the corresponding address and its complement are accessed along with the stored data in the secondary storage table memory 160. If only one entry from the RAM side is accessed, an XOR of each returned address bit and its complement should result in a logic “1” for each address position. If more than one RAM side entry is accessed, the per bit XOR will not result in a logic “1” for each bit position. In this way, a multiple hit in the CAM array 100 may be detected.
While this solution provides a useful mechanism for detecting a multiple hit condition in a CAM structure, the solution requires the addition of a ROM table and its associated circuitry for multiple hit condition detection. In systems where chip area is of concern, the addition of such circuitry and logic causes a decrease in the available area for other functional logic. Moreover, the additional logic and circuitry requires additional power to operate. Furthermore, the solution increases the delay associated with CAM accesses because the solution requires one ROM access, one XOR, and one AND stage of delay in order to perform the multiple hit detection.